#include <vector>
#include <queue>
#include <iostream>

using namespace std;


class Solution {
public:
    // 大顶堆做法 O(n + k log n)  O(n)
    // 会比排序后的做法 O(n log n) 快一些
    int findKthLargest(vector<int>& nums, int k) {  // O(k log n)
        // Type 数据类型, Container 容器类型, Functional 排序方式
        priority_queue<int, vector<int>, less<int>> pq;  // MaxHeap
        for (int n : nums) pq.emplace(n);
        
        int res = -1;
        for (int i=1; i<=k; i++) {
            if (i == k) {
                res = pq.top();
                break;
            } else {
                pq.pop();
            }
        }

        return res;
    }

    // 小顶堆做法 O(n log k)  O(k)
    // 只用 k 个容量！
    int findKthLargestMinHeap(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq;  // MinHeap
        int size = 0;
        while (size < k) pq.emplace(nums[size++]);  // 先插入 k 个元素
        for (int i=size; i<nums.size(); ++i) {
            if (nums[i] > pq.top()) {
                pq.pop();
                pq.emplace(nums[i]);
            }
        }
        return pq.top();
    }

    // 自己实现 PQ 的做法
    void maxHeapify(vector<int>& pq, int i, int heapSize) {
        int l = i*2+1, r = i*2+2, largest = i;
        if (l < heapSize && pq[l] > pq[largest]) {
            largest = l;
        }
        if (r < heapSize && pq[r] > pq[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(pq[i], pq[largest]);
            maxHeapify(pq, largest, heapSize);
        }
    }

    void buildMaxHeap(vector<int>& pq, int heapSize) {
        for (int i=heapSize/2; i>=0; i--) {
            maxHeapify(pq, i, heapSize);
        }
    }

    int findKthLargestMy(vector<int>& nums, int k) {
        int heapSize = nums.size();
        buildMaxHeap(nums, heapSize);
        for (int i=nums.size()-i; i>=nums.size() - k + 1; --i) {
            swap(nums[0], nums[i]);  // 放到末尾相当于删除了
            --heapSize;  // 相当于删掉最后一个元素
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }
};


int main(void) {
    Solution soln = Solution();
    vector<int> arg1{3,2,1,5,6,4};
    int arg2 = 2;
    
    cout << soln.findKthLargest(arg1, arg2);
}
